/****************************************************************************
 **
 ** Copyright (C) 2004-2008 Trolltech ASA. All rights reserved.
 **
 ** This file is part of the documentation of the Qt Toolkit.
 **
 ** This file may be used under the terms of the GNU General Public
 ** License versions 2.0 or 3.0 as published by the Free Software
 ** Foundation and appearing in the files LICENSE.GPL2 and LICENSE.GPL3
 ** included in the packaging of this file.  Alternatively you may (at
 ** your option) use any later version of the GNU General Public
 ** License if such license has been publicly approved by Trolltech ASA
 ** (or its successors, if any) and the KDE Free Qt Foundation. In
 ** addition, as a special exception, Trolltech gives you certain
 ** additional rights. These rights are described in the Trolltech GPL
 ** Exception version 1.2, which can be found at
 ** http://www.trolltech.com/products/qt/gplexception/ and in the file
 ** GPL_EXCEPTION.txt in this package.
 **
 ** Please review the following information to ensure GNU General
 ** Public Licensing requirements will be met:
 ** http://trolltech.com/products/qt/licenses/licensing/opensource/. If
 ** you are unsure which license is appropriate for your use, please
 ** review the following information:
 ** http://trolltech.com/products/qt/licenses/licensing/licensingoverview
 ** or contact the sales department at sales@trolltech.com.
 **
 ** In addition, as a special exception, Trolltech, as the sole
 ** copyright holder for Qt Designer, grants users of the Qt/Eclipse
 ** Integration plug-in the right for the Qt/Eclipse Integration to
 ** link to functionality provided by Qt Designer and its related
 ** libraries.
 **
 ** This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
 ** INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
 ** A PARTICULAR PURPOSE. Trolltech reserves all rights not expressly
 ** granted herein.
 **
 ** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 ** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 **
 ****************************************************************************/

#include <QtCore>
#include <fstream>
#include <string>
#include <cassert>
#include <time.h>

#include "piecegenerator.h"

PieceGenerator::~PieceGenerator()
{
}

FilePieceGenerator::FilePieceGenerator(const char *filename) :
    stream(filename)
{
}

FilePieceGenerator::~FilePieceGenerator()
{
    if (stream.is_open())
        stream.close();
}

const int * FilePieceGenerator::getNextPiece(int &numBlocks)
{
    char buffer[128];
    stream.getline(buffer, 128);

    if (!stream.is_open() || stream.eof()) {
        numBlocks = 0;
        return 0;
    }

    std::string str(buffer);

    switch (str.size ()) {
    case 16: numBlocks = 4; break;
    case 25: numBlocks = 5; break;
    case 36: numBlocks = 6; break;
    case 49: numBlocks = 7; break;
    default: assert(0); break;
    }

    int block = 0;
    for (int i = 0; i < numBlocks; ++i) {
        for (int j = 0; j < numBlocks; j++) {
            if (block >= 14)
                return pieceBuffer;

            if (str[i * numBlocks + j] == '1') {
                pieceBuffer[block++] = i;
                pieceBuffer[block++] = j;
            }
        }
    }

    return pieceBuffer;
}

void FilePieceGenerator::reset()
{
    if (stream.is_open())
        stream.seekg(0, std::ios::beg);
}

RandomPieceGenerator::RandomPieceGenerator()
{
    qsrand(time(0));
}

const int * RandomPieceGenerator::getNextPiece(int &numBlocks)
{
    switch (qrand() % 4) {
    case 0: numBlocks = 4; return pieceCoords4[qrand() % 7];
    case 1: numBlocks = 5; return pieceCoords5[qrand() % 18];
    case 2: numBlocks = 6; return pieceCoords6[qrand() % 60];
    case 3: numBlocks = 7; return pieceCoords7[qrand() % 195];
    }

    return 0;
}

int RandomPieceGenerator::pieceCoords4[7][8] = {
    { 0, 0, 1, 0, 2, 0, 3, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1 },
    { 0, 0, 0, 1, 1, 0, 1, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1 },
    { 0, 1, 1, 0, 1, 1, 2, 0 }
};

int RandomPieceGenerator::pieceCoords5[18][10] = {
    { 0, 0, 1, 0, 2, 0, 3, 0, 4, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 3, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 3, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 0 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 3, 1 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 2, 1 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 2, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 2, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 2, 2 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 2 },
    { 0, 1, 1, 0, 1, 1, 2, 0, 3, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 0 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 2, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 1 }
};

int RandomPieceGenerator::pieceCoords6[60][12] = {
    { 0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 3, 0, 4, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 3, 0, 4, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 0, 4, 0 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 3, 1, 4, 0 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 4, 1 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 0, 3, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 2, 1, 3, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 3, 0, 3, 1 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 2, 0, 3, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 3, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 3, 0, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 0, 3, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 0, 3, 1 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 3, 0 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 3, 1, 4, 1 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 3, 1, 3, 2 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 0, 2, 1 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 1, 1, 2, 0 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 2, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 2, 1, 3, 1 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 2, 0, 2, 1 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 2, 1, 2, 2 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1 },
    { 0, 0, 0, 2, 1, 0, 1, 1, 1, 2, 2, 0 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 1, 4, 1 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 3, 1 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 1, 3, 2 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 3, 2 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 2, 1 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 1, 2, 2 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 2, 2 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 1, 2, 1, 3 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 1, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 3, 1, 3, 2 },
    { 0, 0, 0, 2, 1, 0, 1, 1, 1, 2, 2, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 3, 2 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 2, 3 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 2 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 2, 2, 3 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 3 },
    { 0, 1, 1, 0, 1, 1, 2, 0, 3, 0, 4, 0 },
    { 0, 1, 1, 0, 1, 1, 2, 0, 2, 1, 3, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 0, 3, 0 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 3, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0 },
    { 0, 3, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 1, 3, 1 },
    { 0, 1, 1, 0, 1, 1, 2, 1, 2, 2, 3, 1 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 2 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 2, 2, 3 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 2, 1, 3, 1 },
    { 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3 },
    { 0, 0, 0, 1, 0, 2, 1, 2, 1, 3, 1, 4 }
};

int RandomPieceGenerator::pieceCoords7[195][14] = {
    { 0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 3, 0, 4, 0, 5, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 0, 4, 0, 5, 0 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 3, 1, 4, 0, 5, 0 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 4, 1, 5, 0 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 5, 1 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 0, 3, 0, 4, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 2, 1, 3, 0, 4, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 3, 0, 3, 1, 4, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 3, 0, 4, 0, 4, 1 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 2, 0, 3, 0, 4, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 3, 0, 4, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 3, 0, 3, 1, 4, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 3, 0, 4, 0, 4, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 0, 3, 0, 4, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 0, 3, 1, 4, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 0, 4, 0, 4, 1 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 3, 0, 4, 0 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 3, 1, 4, 0, 4, 1 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 3, 1, 3, 2, 4, 0 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 4, 1, 5, 1 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 4, 0, 4, 1, 4, 2 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 0, 2, 1, 3, 0 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 0, 3, 0, 3, 1 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 1, 1, 2, 0, 3, 0 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 2, 0, 3, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 2, 1, 3, 0, 3, 1 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 2, 0, 2, 1, 3, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 2, 1, 2, 2, 3, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 3, 0, 3, 1, 4, 1 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 2, 0, 3, 0, 3, 1 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 3, 0, 3, 1, 3, 2 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 1, 2, 2, 0, 3, 0 },
    { 0, 0, 0, 1, 0, 2, 0, 3, 1, 0, 2, 0, 3, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 3, 0, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 3, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 2, 3, 0 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 3, 0, 3, 1, 4, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 0, 3, 0, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 3, 0, 3, 1, 3, 2 },
    { 0, 0, 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 3, 0 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 3, 0 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0, 3, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 0, 3, 1, 4, 1 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 3, 0, 3, 1 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 0, 3, 1, 3, 2 },
    { 0, 0, 1, 0, 1, 2, 2, 0, 2, 1, 2, 2, 3, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 3, 0, 3, 2 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 2, 3, 3, 0 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 3, 1, 4, 1, 5, 1 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 3, 1, 3, 2, 4, 1 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 3, 1, 4, 1, 4, 2 },
    { 0, 0, 1, 0, 2, 0, 2, 2, 3, 0, 3, 1, 3, 2 },
    { 0, 0, 1, 0, 2, 0, 3, 0, 3, 1, 3, 2, 4, 2 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 1, 1, 2, 0, 2, 1 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 0, 2, 1, 2, 2 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 2, 1, 3, 1, 4, 1 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 2, 0, 2, 1, 3, 1 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 2, 1, 2, 2, 3, 1 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 2, 1, 3, 1, 3, 2 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 2, 0, 2, 1, 2, 2 },
    { 0, 0, 0, 1, 1, 0, 2, 0, 2, 1, 2, 2, 3, 2 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 1, 2, 1, 3, 2, 0 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 2, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 3, 1, 3, 2 },
    { 0, 0, 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0, 2, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 2, 3, 2 },
    { 0, 0, 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2 },
    { 0, 0, 0, 2, 0, 3, 1, 0, 1, 1, 1, 2, 2, 0 },
    { 0, 0, 0, 2, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 3, 2 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0, 2, 2 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 2, 3 },
    { 0, 0, 0, 3, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0, 2, 3 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 0 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 3, 1, 4, 1 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 1, 3, 2, 4, 1 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 1, 4, 1, 4, 2 },
    { 0, 0, 1, 0, 1, 2, 2, 0, 2, 1, 2, 2, 3, 1 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 3, 1, 3, 2 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 2, 3, 3, 1 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 1, 3, 2, 4, 2 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 3, 1, 3, 2, 3, 3 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 3, 2, 4, 2 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 2, 3, 3, 2 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 3, 2, 3, 3 },
    { 0, 0, 1, 0, 2, 0, 2, 1, 2, 2, 2, 3, 3, 3 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 2, 1, 3, 1 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 1, 2, 2, 3, 1 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 1, 3, 1, 3, 2 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 2, 1, 2, 2 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 1 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 1, 2, 2, 3, 2 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 3 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 2 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 2, 2, 2, 3 },
    { 0, 0, 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 3 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 1, 2, 1, 3, 2, 2 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 1, 2, 2, 2, 2, 3 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 1, 2, 1, 3, 2, 3 },
    { 0, 0, 0, 1, 0, 2, 1, 0, 1, 2, 1, 3, 1, 4 },
    { 0, 0, 0, 1, 0, 2, 0, 3, 1, 0, 1, 3, 1, 4 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 3, 0, 3, 1, 4, 0 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 1, 3, 0, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 3, 0, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 1, 3, 1, 4, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 3, 1, 4, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 3, 1, 3, 2, 4, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 3, 1, 4, 1, 4, 2 },
    { 0, 0, 0, 2, 1, 0, 1, 1, 1, 2, 2, 1, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 1, 2, 2, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 1, 3, 1, 3, 2 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 1, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 2, 3, 3, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 3, 1, 3, 2, 4, 2 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 3, 1, 3, 2, 3, 3 },
    { 0, 0, 0, 2, 1, 0, 1, 1, 1, 2, 1, 3, 2, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 1, 2, 2 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 1, 2, 2, 2, 3 },
    { 0, 0, 0, 3, 1, 0, 1, 1, 1, 2, 1, 3, 2, 1 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 1, 2, 3 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 1 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 2, 3, 3, 2 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 3, 2, 3, 3 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 2, 3, 3, 3 },
    { 0, 0, 1, 0, 1, 1, 2, 1, 2, 2, 2, 3, 2, 4 },
    { 0, 0, 0, 2, 1, 0, 1, 1, 1, 2, 1, 3, 2, 2 },
    { 0, 0, 0, 2, 1, 0, 1, 1, 1, 2, 2, 2, 2, 3 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 2, 3, 2 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 2 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 2, 3, 2, 3, 3 },
    { 0, 0, 0, 3, 1, 0, 1, 1, 1, 2, 1, 3, 2, 2 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 2 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 2, 2, 2, 3, 2, 4 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 3 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 2, 3, 2, 4 },
    { 0, 0, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 4 },
    { 0, 1, 1, 0, 1, 1, 2, 0, 3, 0, 4, 0, 5, 0 },
    { 0, 1, 1, 0, 1, 1, 2, 0, 2, 1, 3, 0, 4, 0 },
    { 0, 1, 1, 0, 1, 1, 2, 0, 3, 0, 3, 1, 4, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 0, 3, 0, 4, 0 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 3, 0, 4, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 3, 0 },
    { 0, 1, 1, 0, 1, 1, 2, 0, 2, 1, 2, 2, 3, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 3, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0, 3, 0 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 3, 0 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 3, 0 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0, 3, 0 },
    { 0, 3, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0, 3, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 3, 1 },
    { 0, 1, 1, 0, 1, 1, 2, 0, 2, 1, 2, 2, 3, 1 },
    { 0, 1, 1, 0, 1, 1, 2, 0, 2, 1, 3, 1, 3, 2 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0, 2, 2 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 2, 3 },
    { 0, 1, 0, 3, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 0 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 3, 1 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 1, 3, 2, 0, 2, 2 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 2, 0, 2, 2, 2, 3 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 0 },
    { 0, 3, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 0 },
    { 0, 4, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 0 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 1, 3, 1, 4, 1 },
    { 0, 1, 1, 0, 1, 1, 2, 1, 2, 2, 3, 1, 4, 1 },
    { 0, 1, 1, 0, 1, 1, 2, 1, 3, 1, 3, 2, 4, 1 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 1, 3, 1 },
    { 0, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 3, 3, 1 },
    { 0, 1, 1, 0, 1, 1, 2, 1, 2, 2, 2, 3, 3, 2 },
    { 0, 1, 1, 0, 1, 1, 2, 1, 2, 2, 3, 2, 3, 3 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 2, 3, 2 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 2, 3, 2, 3, 3 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 2 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 2, 2, 2, 3, 2, 4 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 3 },
    { 0, 1, 1, 0, 1, 1, 1, 2, 1, 3, 2, 3, 2, 4 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 2, 1, 3, 1, 4, 1 },
    { 0, 0, 0, 1, 1, 1, 1, 2, 1, 3, 2, 1, 3, 1 },
    { 0, 0, 0, 1, 1, 1, 2, 1, 2, 2, 2, 3, 3, 1 },
    { 0, 0, 0, 1, 1, 1, 2, 1, 2, 2, 3, 2, 3, 3 },
    { 0, 0, 0, 1, 1, 1, 1, 2, 1, 3, 2, 2, 3, 2 },
    { 0, 0, 0, 1, 1, 1, 1, 2, 1, 3, 1, 4, 2, 2 },
    { 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 2, 4 },
    { 0, 0, 0, 1, 1, 1, 1, 2, 1, 3, 2, 3, 2, 4 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 2 },
    { 0, 2, 1, 0, 1, 1, 1, 2, 2, 2, 2, 3, 2, 4 },
    { 0, 0, 0, 1, 0, 2, 1, 2, 2, 2, 2, 3, 2, 4 },
    { 0, 0, 0, 1, 0, 2, 1, 2, 1, 3, 1, 4, 1, 5 }
};
